Storage devices based on flash memories have become very attractive in the last years; for example, they are commonly used as mass memories (also known as solid-state mass memories) in several data processing systems. These storage devices are compact, robust and with low power consumption; therefore, they may be advantageous, especially in portable systems (such as mobile telephones), which are typically supplied by batteries.
Typically, flash memories used to implement the above-mentioned storage devices can be erased only in blocks having a relatively large size (for example, 16-32 Kbytes). Therefore, once data has been written into the flash memory, this data cannot be updated unless the corresponding whole block is erased. In order to emulate operation of a random access device (such as a standard hard-disk), a translation layer is provided on top of the flash memory. The translation layer manages any update of the data stored in the flash memory by writing a new version thereof in a different area of the flash memory, and at the same time updating corresponding mapping information.
A problem of the storage devices based on flash memories is that they may remain in an inconsistent condition when a power loss occurs during their operation. The risk is particularly high when the storage devices are used in portable systems (since they typically work in harsh environments).
For example, this may happen during a garbage collection procedure. The garbage collection procedure is used to recover the space taken by the old versions of the data stored in a generic block of the flash memory (being not valid any longer), when this block is full. For this purpose, the last version of the data stored in the (old) block is copied into a new block; at the end of the operation, the old block is erased and the mapping information is accordingly updated. Typically, as described in US-A-2006/0161723 (the entire disclosure of which is herein incorporated by reference), additional blocks of the flash memory are used for storing further versions of the data when the corresponding block is full, so as to implement a tree structure; in this way, it is possible to delay the execution of the garbage collection procedure. Nevertheless, when the tree structure reaches a predefined maximum number of levels, the space taken by the old versions of the data stored in the blocks of the tree structure is again be recovered; as above, the last version of the data stored in the old blocks is copied into a new block, and all the old blocks are erased (thus updating the mapping information).
In any case, a power loss during the garbage collection procedure may leave conflicting blocks in the flash memory for the same data. Moreover, the problem is magnified by the above-mentioned tree structure, since the data is collected from multiple blocks that are all erased at the end so that the garbage collection procedure takes a longer time.
Similar problems may be caused when the power loss occurs during a procedure for moving data stored in the flash memory, during a procedure for writing data into the flash memory, or during a procedure for erasing its blocks. In this case as well, the flash memory may remain in an inconsistent condition.
An approach that has been used to solve the above-mentioned problem is of providing a backup structure, which maintains the required power supply during each procedure involving any update of the stored data (even in case of power loss). However, this solution requires additional dedicated hardware, so that it may be burdensome on the structure of the storage device.
With reference in particular to the power loss during the garbage collection procedure, US-A-2006/0161723 also proposes associating a root counter with each block implementing a root node of the tree structure, which root counter is incremented whenever the data is copied from the old blocks to the new block. In this way, if two conflicting root blocks are found after the power loss, it is possible to discard the old one with the lower root counter. However, it has been noted that this solution is not completely satisfactory. Indeed, the use of the root counter does not allow restoring the storage device in any situation (for example, when the power loss occurred when the copying of the data was still in progress).
Another approach that has been used for the power loss during the writing procedure is of reading back the data after its writing; when the written data matches the desired value, it is validated by writing a specific flag into the flash memory. In any case, this solution requires an additional read procedure and an additional writing procedure; therefore, it may have a deleterious effect on the performance of the storage device.